package LeetCode刷题;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-08 16:25
 * @description: Functions of this class is
 * 给你一个整数数组 nums ，数组中的元素“互不相同”。返回该数组所有可能的子集（幂集）。
 * 解集“不能”包含重复的子集。你可以按“任意顺序”返回解集
 * <p>
 * 官方题解：
 * 方法一：可以用数组长度一样的长的二进制数的每一位代指该数字是否出现在子集中，如果数组长度为3的 011 即表示含数组第二三位的子集
 * <p>
 * 方法二：递归法***以后遇到这种全排列的都可以用这这种算法来去弄
 * <p>
 * //集合中每个元素的选和不选，构成了一个满二叉状态树，比如，左子树是不选，右子树是选，
 * 从根节点、到叶子节点的所有路径，构成了所有子集。可以有前序、中序、后序的不同写法，结果的顺序不一样。本质上，其实是比较完整的中序遍历。
 * class Solution {
 * public List<List<Integer>> subsets(int[] nums) {
 *      List<Integer> sub=new ArrayList<>();
 *         List<List<Integer>>ans=new ArrayList<>();
 *         ans.add(sub);
 *         dfs(0,nums,sub,ans);//从0开始递归
 *         return ans;
 *     }
 *     private void dfs(int index,int nums[],List<Integer> sub,List<List<Integer>>ans){
 *         // 1 2 3
 *         if(index==nums.length){
 *             return;//如果索引号到达了边界了就返回
 *         }
 *         //来到这里的时候，要讲之前的添加进子集中的元素放入到新的子集中，这样才能累积多个元素放入到子集中
 *         sub=new ArrayList<Integer>(sub);
 *
 *         //看作一棵二叉树来进行中序遍历
 *         dfs(index+1,nums,sub,ans);
 *         sub.add(nums[index]);
 *         ans.add(sub);
 *         dfs(index+1,nums,sub,ans);
 *     }
 * }
 **/
public class No子集 {
    public static void main(String args[]) {
        System.out.println(subsets(new int[]{1, 2, 3}));
    }


    public static List<List<Integer>> subsets(int[] nums) {
//        //二进制做法
//        List<List<Integer>> ans = new ArrayList<>();
//        List<Integer> sub = new ArrayList<>();
//        ans.add(sub);//先将空集放入到答案集合中
//
//        int maxNum= (int) Math.pow(2,nums.length)-1;//数组真子集的个数=2的数组长度次幂再减一
//        int temp=maxNum;//设置一个临时的变量，用来存储数组每次割分子集的位置
//        //3 -> 000 001 010 011 100 101 110 111
//
//        for(int i=0;i<maxNum;i++){
//            sub=new ArrayList<>();//每次申请一个子集的存储空间
//
//            for(int j=temp,bit=0;bit<nums.length;j>>=1,bit++){//每次通过判断临时变量中1的位置，来确定数组割分出子集中的数
//                if((j&1)==1){//将临时变量二进制位数为1的那个位置，在原数组上的数字放入到子集中
//                    sub.add(nums[bit]);
//                }
//            }
//            ans.add(sub);
////            System.out.println(ans);
//            temp--;//每次都把临时变量减一，达到改变每次子集中数字的做法
//        }


        //回溯做法 类似于一颗二叉树
        List<Integer> sub = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs(0, nums, sub, ans);//从0开始递归
        return ans;
    }

    private static void dfs(int index, int nums[], List<Integer> sub, List<List<Integer>> ans) {
//        // 1 2 3
//        if(index==nums.length){
//            return;//如果索引号到达了边界了就返回
//        }
//        //来到这里的时候，要讲之前的添加进子集中的元素放入到新的子集中，这样才能累积多个元素放入到子集中
//        sub=new ArrayList<Integer>(sub);
//
//        //看作一棵二叉树来进行中序遍历
//        dfs(index+1,nums,sub,ans);
//
//        sub.add(nums[index]);
//        ans.add(sub);
//        dfs(index+1,nums,sub,ans);
        if (index == nums.length) {
            ans.add(new ArrayList<Integer>(sub));
            return;
        }
        sub.add(nums[index]);//如果取index下的数字的话 就放到sub中
        dfs(index + 1, nums,sub,ans);//继续递归

        sub.remove(sub.size() - 1);
        dfs(index + 1, nums,sub,ans);
    }
}